
#include <stdio.h>
#include <stdlib.h>

int main_(int argc, char **argv) {

    int m,i,sum=0;
    printf("Enter the number of Coupons\n");
    scanf("%d",&m);

    //random simulation
    radom_coupon(m);

    int values[m];
    float prob_values[m];
    
    printf("\nEnter  the coupon frequencies for %d coupons\n",m);
    for(i=0;i<m;i++)
    {
        scanf("%d",&values[i]);
        sum=sum+values[i];
    }
    printf("\nEnterd  coupon probabilities for %d coupons are\n",m);
    for(i=0;i<m;i++)
    {
      prob_values[i]=(float)values[i]/sum;
      printf("%f\t",prob_values[i]);
    }

    //powerset approach
    powerset(m,prob_values);
    exit(0);
}


void radom_coupon(int m)
{
    int i,j,draw_count=0,coupons_count=0;
    int experiment_count=0;
    float average_draw=0;
    int coupons[m];
    srand(100);
    printf("\nEnter number of experiment for random simulation");
    scanf("%d",&experiment_count);
    for(i=0;i<experiment_count;i++)
    {
      coupons_count=0;
      draw_count=0;

      for(j=0;j<m;j++)
      {
        coupons[j]=0;
      }
      while(1)
      {
        int random_num=rand()%m;
        draw_count++;
        //printf("rad num :%d\n",random_num);
        if(coupons[random_num]==0)
        {
          //printf("\n count: %d\t coupon :%d",draw_count,coupons[random_num]);
          coupons_count++;
          coupons[random_num]=1;
          if(coupons_count==m){
            //printf("coupons collected %d",draw_count);
            break;
          }
        }
      }
      //printf("\n %d Set of coupons collected after %d draw",i+1,draw_count);
      average_draw=average_draw+draw_count;
    }
    printf("\nOn an average %f number of coupons draw needed to collect all coupons",average_draw/experiment_count);
}


void  powerset(int argc, float argv[])
{
    int i, j,k, bits,i_max = 1U << argc;
    float totalsubsum=1;
    
    for (i = 0; i < i_max-1 ; ++i)
    {
        int len = bitcount(i);
        float subsum=0.0;
        //printf("\n{");
                float subset[len];
                for (bits = i, j = 0,k=0; bits; bits >>= 1, ++j)
                {
                        if (bits & 1)
                        {
                                //printf(bits > 1 ? "%d, " : "%d", argv[j]);
                                subset[k]=argv[j];
                                //printf("\t el:%d",subset[k]);
                                //printf("\t ele:%d",*( pset[i-1] +k));
                                subsum=subsum-subset[k];
                                //printf("\nsubsum %f, ele %f",subsum,subset[k]);
                                k++;
                        }
                }
         //printf("}\n");
         if(len>0)
         {
	    if( len%2==0){
	    	totalsubsum=totalsubsum+(1/(1+subsum));
	    	//printf("\n 1/(1+subsum) %f",1/(1+subsum));
	    }
	    else{
	      totalsubsum=totalsubsum-(1/(1+subsum));
	      	//printf("\n 1/(1+subsum) %f",1/(1+subsum));
	    }
	 }
         // printf("\nsubset sub : %f, total sum : %f",subsum,totalsubsum);
    }
    printf("\n By Power set method the answer is : %f ",fabsf(totalsubsum));
}


int bitcount(unsigned int n)
{       int c=0;
   for(c=0;n;c++)
   {
     n=n&(n-1);
    // printf("%d",n);
   }
   //printf("%d : ",c);
   return c;
}
